package 中等.模拟;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 你有一个单词列表 words 和一个模式  pattern，你想知道 words 中的哪些单词与模式匹配。
 * 如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，我们就得到了
 * 所需的单词，那么单词与模式是匹配的。
 * （回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个
 * 字母映射到同一个字母。）
 * 返回 words 中与给定模式匹配的单词列表。
 * 你可以按任何顺序返回答案。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-and-replace-pattern
 */
public class 查找和替换模式_890 {

    public static void main(String[] args) {

        String[] words = {"abc", "deq", "mee", "aqq", "dkd", "ccc"};
        System.out.println(findAndReplacePattern(words, "abb"));

    }

    /**
     * 优化思路
     * word 映射 pattern ，确保 word[i] -> pattern[i] 唯一
     * pattern 映射 word ，确保 pattern[i] -> word[i] 唯一
     *
     * @param words
     * @param pattern
     * @return
     */
    public static List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> list = new ArrayList<>();
        for (String word : words) {
            Map<Character, Character> map = new HashMap<>();
            int[] count = new int[26];
            if (word.length() != pattern.length()) continue;
            boolean flag = true;
            for (int i = 0; i < word.length(); i++) {
                char w = word.charAt(i);
                char p = pattern.charAt(i);
                if (map.containsKey(p) && map.get(p) != w) {
                    flag = false;
                    break;
                } else if (!map.containsKey(p) && count[w - 'a'] == 1) {
                    flag = false;
                    break;
                }
                map.put(p, w);
                count[w - 'a']++;
            }
            if (flag) list.add(word);
        }
        return list;
    }

}
